package jacktgq.mazeSolver.solve;

import jacktgq.AlgoVisHelper;

import java.awt.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class AlgoVisualizer {
    private AlgoFrame frame;
    private boolean isAnimated = true;
    private MazeData mazeData;

    private static final int BLOCK_WIDTH = 8;
    private static final int BLOCK_HEIGHT = 8;
    private static final int DELAY = 2;

    public AlgoVisualizer(String filename, int sceneWidth, int sceneHeight){
        mazeData = new MazeData(filename);
        // mazeSolver();
        // System.out.println(mazeData);
        // 初始化视图
        EventQueue.invokeLater(() -> {
            frame = new AlgoFrame("迷宫游戏", sceneWidth, sceneHeight, mazeData);
            /*frame.addKeyListener(new AlgoKeyListener());
            frame.addMouseListener(new AlgoMouseListener());*/
            new Thread(() -> {
                run();
            }).start();
        });
    }

    // 记录二维数组中的元素的遍历状态和上一个元素的位置
    private Position[][] prevs;

    boolean hasReachedEnd = false;
    public void mazeSolver() {
        prevs = new Position[mazeData.getM()][mazeData.getN()];
        // 从起始点（0，1）出发，使用深度优先遍历的方式求解迷宫
        // dfs(0, 1, 0, 1);

        // 如果已经到底终点，就找出这个路径
        if (hasReachedEnd) {
            System.out.println("迷宫有解！");
        } else {
            System.out.println("迷宫无解！");
        }
    }

    // 四个方向的偏移量数组
    private int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    /**
     * 深度优先遍历方式求迷宫的解
     * @param x     ：起始所在行数
     * @param y     ：起始所在列数
     * @return
     */
    public boolean goWithDFS(int x, int y) {
        mazeData.visited[x][y] = true;
        setData(x, y, true);

        if (x == mazeData.getExitX() && y == mazeData.getExitY()) {
            return true;
        }

        // 去4个方向深度优先遍历
        for (int i = 0; i < dirs.length; i++) {
            int nextX = x + dirs[i][0];
            int nextY = y + dirs[i][1];
            // 继续寻找下一个位置必须满足下面三个条件
            // 1. 位置必须合法，没有超出边界
            // 2. 下一个位置没有被遍历过
            // 3. 下一个位置是路
            if (mazeData.inArea(nextX, nextY) && !mazeData.visited[nextX][nextY] && mazeData.getMazeDataAt(nextX, nextY) == MazeData.ROAD) {
                // 找到终点，记录一下
                if(goWithDFS(nextX, nextY)) {
                    return true;
                }
            }
        }

        setData(x, y, false);
        return false;
    }

    /**
     * 深度优先遍历方式求迷宫的解
     * @return
     */
    public boolean goWithDFSNonrecursive() {
        Stack<Position> stack = new Stack<>();
        int x = mazeData.getEntranceX();
        int y = mazeData.getEntranceY();
        stack.push(new Position(x, y, null));
        mazeData.visited[x][y] = true;
        setData(x, y, true);
        while (!stack.isEmpty()) {
            Position pos = stack.pop();
            x = pos.x;
            y = pos.y;
            setData(x, y, true);

            if (x == mazeData.getExitX() && y == mazeData.getExitY()) {
                findPath(pos);
                return true;
            }

            for (int i = 0; i < dirs.length; i++) {
                int nextX = x + dirs[i][0];
                int nextY = y + dirs[i][1];
                if (mazeData.inArea(nextX, nextY) && !mazeData.visited[nextX][nextY] && mazeData.getMazeDataAt(nextX, nextY) == MazeData.ROAD) {
                    stack.add(new Position(nextX, nextY, pos));
                    mazeData.visited[x][y] = true;
                }
            }
        }

        return false;
    }

    /**
     * 从终点开始向前找出路径
     */
    private void findPath(Position pos) {
        while (pos != null) {
            mazeData.result[pos.x][pos.y] = true;
            // System.out.println(cur);
            pos = pos.prev;
        }
    }

    /**
     * 使用广度优先遍历方式求迷宫的解
     * @return
     */
    private boolean goWithBFS() {
        Queue<Position> queue = new LinkedList<>();
        // 将起始位置入队
        int x = mazeData.getEntranceX();
        int y = mazeData.getEntranceY();
        queue.add(new Position(x, y, null));
        mazeData.visited[x][y] = true;
        setData(x, y, true);
        while (!queue.isEmpty()) {
            Position pos = queue.remove();
            x = pos.x;
            y = pos.y;
            setData(x, y, true);

            if (x == mazeData.getExitX() && y == mazeData.getExitY()) {
                findPath(pos);
                return true;
            }

            for (int i = 0; i < dirs.length; i++) {
                int nextX = x + dirs[i][0];
                int nextY = y + dirs[i][1];
                if (mazeData.inArea(nextX, nextY) && !mazeData.visited[nextX][nextY] && mazeData.getMazeDataAt(nextX, nextY) == MazeData.ROAD) {
                    queue.add(new Position(nextX, nextY, pos));
                    mazeData.visited[nextX][nextY] = true;
                }
            }
        }

        return false;
    }

    // 动画逻辑
    private void run(){
        // 绘制数据
        setData(-1, -1, false);
        // goWithDFS(mazeData.getEntranceX(), mazeData.getEntranceY());
        // goWithDFSNonrecursive();
        // goWithBFS();
        if (goWithBFS()) {
            System.out.println("迷宫有解");
        } else {
            System.out.println("迷宫无解");
        }
        setData(-1, -1, false);
    }

    // 修改可视化数据，并重新渲染
    private void setData(int x, int y, boolean isPath) {
        if (mazeData.inArea(x, y)) {
            mazeData.path[x][y] = isPath;
        }
        frame.render(mazeData);
        AlgoVisHelper.pause(DELAY);
    }

    /*private class AlgoKeyListener extends KeyAdapter{
        @Override
        public void keyReleased(KeyEvent event){
        }
    }

    private class AlgoMouseListener extends MouseAdapter{
        @Override
        public void mouseReleased(MouseEvent event){
        }
    }*/

    public static void main(String[] args) {
        // 绘图区域的宽高要减去边框占用的长度，
        // 宽度 / N，高度 / M 的结果如果是小数，
        // 而宽度和高度的单位是像素不能为小数，只能取整，那么在绘图区域中画的图会有空隙，
        // 所以这里算一个窗口的宽高，让绘制的图显示最完美
        // 窗口左右边框共占用6像素，上下边框占用29像素
        // 101 x 101的迷宫，假设每一格宽度为BLOCK_WIDTH，高度为BLOCK_HEIGHT个像素
        int sceneWidth = BLOCK_WIDTH * 101 + 6;
        int sceneHeight = BLOCK_HEIGHT * 101 + 29;
        String filename = "data/maze_101_101.txt";
        AlgoVisualizer visualizer = new AlgoVisualizer(filename, sceneWidth, sceneHeight);
    }
}
